1. Field of the Invention
This invention relates to functional design verification. More particularly, this invention relates to the generation of an initial state of a design under verification (DUV) in order to produce subsequent transactions for use in verifying the design and to enhance their quality.
2. Description of the Related Art
Functional verification is widely acknowledged to be a bottleneck in the hardware design cycle. Indeed, up to 70% of design development time and resources are typically spent on functional verification. Allowing users to find design flaws, and fixing them in a subsequent release would be unwise and costly for three main reasons: (1) harm to reputation and brand-name; (2) a high cost of recall and replacement when there is a large installed base; and (3) litigation in the event that design flaws caused injury.
In current industrial practice, dynamic verification is the main functional verification technique for large and complex designs. Dynamic verification is accomplished by generating a large number of tests using random test generators, simulating the tests on the design-under-verification, and checking that the design-under-verification behaves according to its specification.
The rationale behind verification by simulation is that one acquires confidence in the correctness of a design-under-verification by running a set of test cases that encompass a sufficiently large number of different cases, which in some sense is assumed to be a representative sample of the full space of possible cases. The ability of the design-under-verification to correctly handle all cases is inferred from the correct handling of the cases actually tested. This approach is discussed, for example, in the document User Defined Coverage—A Tool Supported Methodology for Design Verification, Raanan Grinwald, Eran Harel, Michael Orgad, Shmuel Ur, and Avi Ziv, Proc. 38th Design Automation Conference (DAC38), pp 158-163, 1998. When conducting simulations, it is desirable to define a particular subspace, which is considered to be interesting in terms of verification, and then to generate tests selected at random that cover the subspace.
The term “coverage” concerns checking and showing that testing has been thorough. Coverage is any metric of completeness with respect to a test selection criterion for the design-under-verification. Simply stated, the idea is to create in some systematic fashion a large and comprehensive list of tasks, and check that in the testing phase each task was executed.
The need to create a wide spread of behaviors in the DUV exists whether explicit coverage models exist or not. In that sense, one of the requirements from random stimuli generators is to create test cases that cover well the space of possible stimuli that meet user requirements (see the document Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation, E. Bin, R. Emek, G. Shurek, and A. Ziv, IBM Systems Journal, 41(3):386-402, 2002). This requirement holds even if there are no explicit coverage models defined on the generated stimuli.
In recent years, technology has shifted towards constraint-based modeling of the generation task and generation schemes driven by solving constraint satisfaction problems (CSP), as described in the document Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation, E. Bin, R. Emek, G. Shurek, and A. Ziv, IBM Systems Journal, 41(3):386-402, 2002. Validity of the stimuli, their quality, and test specification requirements are naturally modeled through constraints. For CSP to drive stimuli generation, the stimuli, or their building blocks, are modeled as constraint networks. A random stimuli generator can, therefore, be viewed as a CSP solver.
The constraint network resulting from a model of the entire stimuli is, in most cases, too large and complex for CSP solvers to handle. Therefore, most stimuli generators break the constraint network into smaller, loosely coupled networks and solve each of the smaller networks separately, as explained in the above-noted document Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation, and further in the document X-Gen: A Random Test-Case Generator for Systems and SoCs, R. Emek, I. Jaeger, Y. Naveh, G. Bergman, G. Aloni, Y. Katz, M. Farkash, I. Dozoretz, and A. Goldin, in IEEE International High Level Design Validation and Test Workshop, pp 145-150, October 2002. More precisely, the stimuli are broken into a sequence of transactions, and each transaction is generated separately, such that the solution for a subsequent transaction is affected by the state of the system as determined either by initializations or by previous transactions.
For complexity reasons, most stimuli generators use sequential solutions without planning ahead, i.e., considering the requirements of subsequent transactions when solving the constraint network of the current transaction. Therefore, in many cases they fail to find consistent stimuli because of a bad selection of the initial state.